1. Field of the Invention
This invention relates, in general, to networking and, in particular, to a methodology for the formation and maintenance of an ad-hoc network of wireless communication nodes and for routing messages in such a network.
2. Background of the Invention
Large networks of wireless communication nodes are expected to play an increasingly important role in networking sensors or actuators for a variety of applications. Such applications include seismic monitoring, precision agriculture, environmental and atmospheric monitoring, automated electricity, gas and water meter reading, industrial control and automation etc. Each wireless communication node in such networks will have limited range and will only be able to communicate with a few other nodes directly. In all such networks, the ad-hoc formation and maintenance of the network as new nodes join the network and nodes leave the network due to failure or removal is a requirement. The routing of messages from any source node in the network to any other destination node over multiple intermediate nodes or hops is also a further requirement.
Few examples of such ad-hoc network formation and routing exist in the prior art. One example is U.S. Pat. No. 5,987,011, issued to Toh, and incorporated herein for reference. In this patent, the routing methodology used starts with a directed broadcast from the source node. The broadcast message is further broadcast by each node in the network that receives the broadcast message, after modification of the message to include an identifier for the node that performs the further broadcast. Thus, by a repetition of this process, the broadcast reaches the destination node, presumably multiple times. By examining each such received broadcast message, the destination node can find the path that the message took through the network and deduce multiple paths from the source node to the destination node. Then, the destination node informs the source node of the routing paths it deduced through one of such deduced paths, thus enabling the source node to obtain a route to the destination node. A significant shortcoming of this methodology is the amount of traffic it generates since deduction of each route amounts to a flooding of the network. A further shortcoming is that no provision is made for evaluating various parameters of the routes such as latency, energy consumption etc. and for selecting a particular route over others.
U.S. Pat. No. 6,078,269, issued to Markwell, et al., and incorporated herein for reference describes a network of wireless sensor detectors but merely describes the networks as a “CSMA-type” network. Presumably, this implies that each node in the network merely listens for other nodes transmitting and transmits if possible. Thus, no provision is made for ad-hoc network formation, maintenance or routing across multiple hops.
U.S. Pat. No. 5,553,094, issued to Johnson, et al., and incorporated herein for reference describes a network of remote data gathering stations but uses a cellular communication scheme. This type of scheme requires that each of the nodes be in transmitting and receiving range of a base station and is thus a network of a different nature from an ad-hoc, multi-hop network; this patent provides no disclosure of the formation, maintenance or routing of such an ad-hoc multi-hop network.
U.S. Pat. No. 6,028,857, issued to Poor, and incorporated herein for reference, describes the formation and maintenance of a self-organizing network. This patent describes a “contour routing” scheme whereby each node in a network does not maintain a routing table but rather maintains a cost table for every other node. Typically, the cost table will contain a “hop count” value which indicates how many intermediate nodes are present in the path from the originating node to the destination node. When a node wishes to send a message to a destination, it attaches a cost to the message indicating how many hops the message should take to the destination and broadcasts the message to all neighboring nodes. Each of the neighboring nodes then examines the message, determines whether it is nearer to the destination than the originator and, if it is nearer, decrements the cost and again broadcasts to its neighbor. If a node that receives a message for another destination determines it is farther from the destination than the originator, the message is discarded. In this way, through multiple broadcasts, the message reaches its destination. However, it should be noted that during the initial formation of the network, a new node arriving in the network does not yet know the hop count to any destination node. In this case, according to this patent, a new node “floods” the network by sending a flood message that gets broadcast to every other node and to which every other node in the network replies. In this way, a new node learns about every other node in the network. The method described in this patent has two disadvantages. First, during normal operation of network, when a node wishes to send a message to a destination node, it is seen that the message is actually sent, and repeated by every node on every equivalent path from the originating node to the destination node. This is a very inefficient method since multiple unnecessary transmissions occur. Second, a new node joining the network triggers a flood of traffic in the entire network where every single node broadcasts the flood, and, further, each reply, also triggers broadcasts. This again, is an extremely inefficient method. Indeed, in large networks, the entire network may become bogged down a cease to function because of the huge amount of traffic triggered by just one node joining the network. Thus, the method described in this patent has some significant shortcomings that make it unsuitable for large networks.
There is thus a strong need for a methodology that addresses the requirements mentioned earlier of large ad-hoc networks of wireless communication nodes suitable for sensor networking applications.
It is thus an objective of the present invention to provide a methodology that allows for the formation and maintenance of an ad-hoc network of wireless communication nodes. It is a further objective of the present invention to provide for a routing methodology that allows the detection and use of optimum routes between any two nodes in the network based on a variety of criteria.